class LinkNode:
    def __init__(self,data=None):
        self.data=data
        self.next=None
class LinkList:
    def __init__(self):
        self.head=LinkNode()
        self.head.next=None
    def HeadCreateList(self,arr):#头插批量建表
        for i in range(0,len(arr)):
            pnew=LinkNode(arr[i])
            pnew.next=self.head.next
            self.head.next=pnew
    def TailCreateList(self,arr):#尾插批量建表
        tail=self.head
        for i in range(0,len(arr)):
            pnew=LinkNode(arr[i])
            tail.next=pnew
            tail=pnew
        tail.next=None
    def FindNode(self,num):#查找节点
        cur=self.head.next
        i=0
        while(i<num and cur is not None):
            i+=1
            cur=cur.next
        return cur
    def FindIndex(self,x):#查找节点
        cur=self.head.next
        i=0
        while(cur is not None):
            if(cur.data==x):
                return i
            i+=1
            cur=cur.next


    def CreatNode(self, x):#创建新节点
        newnode = LinkNode()
        newnode.data = x
        return newnode

    def HeadInsert(self, x):#头插
        newhead = self.CreatNode(x)
        if (newhead is not None):
             newhead.next = self.head.next
             self.head.next = newhead

    def TailInsert(self,x):#尾插
        newtail=self.CreatNode(x)
        if(newtail!=None):
            tail = self.head.next
            while (tail.next != None):
                tail = tail.next
            tail.next =newtail
    def GetSize(self):#计算大小
        size=0
        cur=self.head.next
        while(cur!=None):
            size+=1
            cur=cur.next
        return size
    def Insert(self,i,x):
        assert(i>=0)
        newnode = self.CreatNode(x)
        if(i==0):
            newnode.next=self.head.next
            self.head.next=newnode
        else:
            pf = self.FindNode(i - 1)
            assert (pf != None)
            newnode.next = pf.next
            pf.next = newnode
    def Delete(self,i):
        assert (i >=0)
        if(i==0):
            self.head.next=self.head.next.next
        else:
            pf = self.FindNode(i - 1)
            assert (pf != None)
            pf.next = pf.next.next

    def DisplayList(self):#打印节点
        p = self.head.next
        while (p is not None):
            print(f"{p.data}->",end=' ')
            p = p.next
        print()
    def AdjustLinkList(self):
        cur=self.head.next
        odd=LinkNode()
        even=LinkNode()
        oddtail=odd
        eventail=even
        while cur != None:
            if cur.data%2!=0:
                oddtail.next=cur
                oddtail=cur
            else:
                eventail.next=cur
                eventail=cur
            cur=cur.next
        oddtail.next=even.next
        eventail.next=None
        self.head.next=odd.next




if __name__ =="__main__":
    L1 = LinkList()
    arr1 = [1, 2, 3, 4, 5]
    arr2 = [1, 2, 3, 4, 5]
    L1.HeadCreateList(arr1)
    # print(L1.FindIndex(5))
    # L1.Insert(0,5)
    # L1.Insert(0,22)
    L1.DisplayList()
    L1.AdjustLinkList()
    L1.DisplayList()
    # L1.Delete(1)
    # L1.Insert(1, 22)
    # L1.DisplayList()
    # L1.TailCreateList(arr2)
    # L1.DisplayList()
    # L1.HeadInsert(2)
    # L1.HeadInsert(4)
    # L1.HeadInsert(6)
    # L1.HeadInsert(8)
    # L1.DisplayList()
    # L1.TailInsert(1)
    # L1.TailInsert(3)
    # L1.TailInsert(5)
    # L1.TailInsert(7)
    # L1.DisplayList()
    print(L1.GetSize())
